package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

public class _19_Solution {

    public int numDecodings(String s) {
        if (s.charAt(0) < '1' || s.charAt(0) > '9') {
            return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for (int i = 1; i < s.length(); i++) {
            char curChar = s.charAt(i);
            if (curChar < '0' || curChar > '9') {
                return 0;
            }
            char preChar = s.charAt(i - 1);
            if (curChar == '0') {
                if (preChar != '1' && preChar != '2') {
                    return 0;
                } else {
                    if (i - 2 >= 0) {
                        dp[i] = dp[i - 2];
                    } else {
                        dp[i] = 1;
                    }
                    continue;
                }
            }
            if ((preChar != '1' && preChar != '2') || (preChar == '2' && curChar > '6')) {
                dp[i] = dp[i - 1];
            } else {
                if (i - 2 >= 0) {
                    dp[i] = dp[i - 1] + dp[i - 2];
                } else {
                    dp[i] = dp[i - 1]+1;
                }

            }
        }
        return dp[dp.length-1];
    }

    @Test
    public void test(){
        String str = "2611055971756562";
        System.out.println(numDecodings(str));
    }
}
